"""
3446. 按对角线进行矩阵排序
中等
相关标签
premium lock icon
相关企业
提示
给你一个大小为 n x n 的整数方阵 grid。返回一个经过如下调整的矩阵：

左下角三角形（包括中间对角线）的对角线按 非递增顺序 排序。
右上角三角形 的对角线按 非递减顺序 排序。


示例 1：

输入： grid = [[1,7,3],[9,8,2],[4,5,6]]

输出： [[8,2,3],[9,6,7],[4,5,1]]

解释：



标有黑色箭头的对角线（左下角三角形）应按非递增顺序排序：

[1, 8, 6] 变为 [8, 6, 1]。
[9, 5] 和 [4] 保持不变。
标有蓝色箭头的对角线（右上角三角形）应按非递减顺序排序：

[7, 2] 变为 [2, 7]。
[3] 保持不变。
示例 2：

输入： grid = [[0,1],[1,2]]

输出： [[2,1],[1,0]]

解释：



标有黑色箭头的对角线必须按非递增顺序排序，因此 [0, 2] 变为 [2, 0]。其他对角线已经符合要求。

示例 3：

输入： grid = [[1]]

输出： [[1]]

解释：

只有一个元素的对角线已经符合要求，因此无需修改。



提示：

grid.length == grid[i].length == n
1 <= n <= 10
-105 <= grid[i][j] <= 105
"""
from typing import List


class Solution:
    def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        """
        贪心?
        :param grid:
        :return:
        """
        def fixOne(grid:List[List[int]],x:int,y:int,sortBool:bool):
            l = []
            len1 = len(grid)
            i = x
            j = y
            while i<len1 and j<len1:
                l.append(grid[i][j])
                i+=1
                j+=1
            l.sort(reverse=sortBool)  # 修正这一行
            i = x
            j = y
            for k in range(len(l)):
                grid[i][j] = l[k]
                i+=1
                j+=1
        len1 = len(grid)
        for i in range(len1-2,-1,-1):
            fixOne(grid,i,0,True)
        for j in range(1,len1-1):
            fixOne(grid,0,j,False)
        return grid


    def sortMatrix_res(self, grid: List[List[int]]) -> List[List[int]]:
        """
        遍历对角线 to_think
        :param grid:
        :return:
        """
        m, n = len(grid), len(grid[0])
        # 第一排在右上，最后一排在左下
        # 每排从左上到右下
        # 令 k=i-j+n，那么右上角 k=1，左下角 k=m+n-1
        for k in range(1, m + n):
            # 核心：计算 j 的最小值和最大值
            # i=0 的时候，j最小，j=n-k，但不能是负数(可以理解为：从右上到左下，每次延伸到x=0轴的情况，只要超过对角线，对角线会映射到左边的区域外，也就是j<0,所以超过都对角线后=0)
            min_j = max(n - k, 0)
            # i=m-1 的时候，j最大，j=m+n-1-k，但不能超过 n-1(可以理解为：从右上到左下，每次延伸到x=m-1轴的情况，未超过对角线时，对角线会映射到右边区域外，也就是j>n-1越界，所以取最大值n-1,
            # 超过都对角线后正常，把k = i - j + n 的i = m-1带入，得到k = m-1-j+n 所以 j = m+n-1-k )
            max_j = min(m + n - 1 - k, n - 1)
            a = [grid[k + j - n][j] for j in range(min_j, max_j + 1)]  # 根据 k 的定义得 i=k+j-n
            a.sort(reverse = min_j==0)
            for j, val in zip(range(min_j, max_j + 1), a):
                grid[k + j - n][j] = val
        return grid

if __name__ == '__main__':
    # print(Solution().sortMatrix([[1,7,3],[9,8,2],[4,5,6]]))
    print(Solution().sortMatrix_res([[1,7,3],[9,8,2],[4,5,6]]))


